package xyz.robinbingo.leetcode.a20.b05.c13;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class Solution {

    Map<Integer, List<Integer>> map = new TreeMap<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        List<Integer> integers = new ArrayList<>();
        integers.add(root.val);
        result.add(integers);
        dfs(root, 0);
        result.addAll(map.values());
        return result;
    }

    private void dfs(TreeNode node, int depth) {
        if (node.left != null) {
            map.computeIfAbsent(depth, k -> new ArrayList<>());
            map.get(depth).add(node.left.val);
            dfs(node.left, depth + 1);
        }
        if (node.right != null) {
            map.computeIfAbsent(depth, k -> new ArrayList<>());
            map.get(depth).add(node.right.val);
            dfs(node.right, depth + 1);
        }
    }

}
